This invention relates to digital data-transfer systems wherein the data is encoded before transfer and then decoded in a manner facilitating error-detection. More particularly, this invention relates to methods and apparatus for encoding and decoding digital data to provide for transferring serial data substantially error-free.
Much effort has been devoted to coding serial digital data in various ways to perform detection and/or correction of the unavoidable errors encountered during data transfer. Prior art coding schemes intend to make the transmitted data less susceptible to errors, through the us of cyclic block-coding, convolutional coding, Hamming, BCH, CRC, Fire, Golay, Reed-Solomon and other complex coding techniques, as is well known in the art. The simplest and most widely-used error detection method is the "parity bit" technique, which appends an additional bit to, say, every 7-bit word, in order to make the number of 1's in the completed 8-bit word even (or odd, as the case may be). Such coding methods, however, although providing useful results in many applications, can be quite deficient in many respects. For example, the single-parity-bit scheme is not capable of detecting words containing an even number of errors. Such errors are common in many data transfer systems. The more complex cyclic and convolutional codes, while providing some error-correction capability, can fail catastrophically if the number of errors exceeds some small value determined by the mathematical properties of the particular code. In such a case, the decoder can unknowingly output a totally erroneous character while assuming that it has instead merely corrected several errors in the received word. Noise which causes the number of errors in a received character to exceed the maximum number which the code can detect is called "catastrophic" noise, due to the inability of the decoding process to know that its maximum number of correctable or detectable errors has been exceeded (see "The Technology of Error-Correcting Codes", E. R. Berlekamp, Proceedings of the IEEE; May, 1980).
One particularly serious problem in many systems is therefore presented by what is called burst noise. Generally, the effect of burst noise on analog systems is to force contiguous strings of 1's (or 0's), often of considerable and unpredictable length, into the recovered encoded stream. This is often the case regardless of the particular analog modulation technique used to transfer the encoded data, such as AM, FM, FSK, PSK, Manchester, Biphase, and other well-known modulation methods. Both high-amplitude noise and/or sudden signal loss can cause clipping, saturation, and other non-linear limiting effects in sensitive analog receives. An ideal error-detection system would have high sensitivity to such perturbations, and would be so sensitive sio as to be able to detect forced strings of 1's (or 0's) of any length, from single-bit errors (a "string" of length 1) to long strings resulting from channel failure (a string of essentially infinite length). Such an optimum error-detecting encoding/decoding process is the subject of this invention.